{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.1 The hiring problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.1-1\n",
    "\n",
    "> Show that the assumption that we are always able to determine which candidate is best, in line 4 of procedure HIRE-ASSISTANT, implies that we know a total order on the ranks of the candidates."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Transitive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.1-2 $\\star$\n",
    "\n",
    "> Describe an implementation of the procedure RANDOM$(a, b)$ that only makes calls to RANDOM$(0, 1)$. What is the expected running time of your procedure, as a function of $a$ and $b$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Divide $[a, b]$ into $[a, mid]$ and $(mid, b]$, if RANDOM$(0, 1)$ gives 0 then we choose $[a, mid]$ and repeat the step until there is only one element left. The expected running time is $\\Theta(\\lg(b-a))$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "\n",
    "def random_interval(a, b):\n",
    "    while a < b:\n",
    "        if random.randint(0, 1) == 0:\n",
    "            b = (a + b) // 2\n",
    "        else:\n",
    "            a = (a + b) // 2 + 1\n",
    "    return a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.1-3 $\\star$\n",
    "\n",
    "> Suppose that you want to output $0$ with probability $1/2$ and $1$ with probability $1/2$. At your disposal is a procedure BIASED-RANDOM, that outputs either $0$ or $1$. It outputs $1$ with some probability $p$ and $0$ with probability $1 - p$, where $0 < p < 1$, but you do not know what $p$ is. Give an algorithm that uses BIASED-RANDOM as a subroutine, and returns an unbiased answer, returning $0$ with probability $1/2$ and $1$ with probability $1/2$. What is the expected running time of your algorithm as a function of $p$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The probabilities of generating (0, 1) and (1, 0) with BIASED-RANDOM is the same. We can generate two numbers with BIASED-RANDOM, and if they are different, we can return the first number, otherwise we should regenerate the two numbers. Since the probability of generating two different number is $2p(1-p)$, thus the expectation of generation times is $\\frac{1}{2p(1-p)}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "\n",
    "def biased_random():\n",
    "    if random.random() < 0.1:\n",
    "        return 0\n",
    "    return 1\n",
    "\n",
    "\n",
    "def unbiased_random():\n",
    "    while True:\n",
    "        a = biased_random()\n",
    "        b = biased_random()\n",
    "        if a != b:\n",
    "            return a"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
